#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <list>
#include <random>
using namespace std;
#define inf 100000000
struct SumDetail
{
    int hitTime;
    int planScore;
    vector<int> tempIds;
    SumDetail()
    {
        hitTime = 0;
        planScore = 0;
        tempIds.push_back(-1);
    }
};
struct Plan
{
    vector<int> ids;
    int remainder;
    int repeat;
    Plan(int size) {
        remainder = 0;
        repeat = 0;
        ids.assign(size, 0); }
};

class CuttingPlanner
{
public:
    CuttingPlanner(int types, int* lengths, int* counts, int rawLength, int maxCombination) : _rawLength(rawLength), _maxCombination(maxCombination)
    {
        int cursor = 0;
        for (size_t i = 0; i < types; i++)
        {
            bool unique = true;
            for (size_t j = 0; j < _lengths.size(); j++)
            {
                if (*(lengths + i) == _lengths[j])
                {
                    unique = false;
                    _counts[j] += *(counts + i);
                }
            }
            if (unique)
            {
                _lengths.push_back(*(lengths + i));
                _counts.push_back(*(counts + i));
                cursor++;
            }
        }
        _types = cursor;
    };
    int* solve(int repeat)
    {
        generateSolution(repeat);
        _retLen = (bestPlan.size() + 1) * (_types + 2);
        int* ret;
        ret = (int*)malloc((_retLen) * sizeof(int));
        for (size_t j = 0; j < _types + 2; j++)
        {
            if (j < _types)
                *(ret + j) = _lengths[j];
            else
                *(ret + j) = 0;
        }
        for (size_t i = 0; i < bestPlan.size(); i++)
        {
            for (size_t j = 0; j < _types + 2; j++)
            {
                int k = (i + 1) * (_types + 2) + j;
                if (j < _types)
                    *(ret + k) = bestPlan[i].ids[j];
                else if (j == _types)
                    *(ret + k) = bestPlan[i].remainder;
                else
                    *(ret + k) = bestPlan[i].repeat;
            }
        }
        return ret;
    }
    int getLen()
    {
        return _retLen;
    }
    void generateSolution(int repeat)
    {
        int notImprovedCount = 0;
        int bestRawCount = inf;        // 最好的方案使用的原材料数
        int bestTail = _rawLength;     // 最好的方案中的最长余料
        vector<int> prodScore(_types); // 给零件评分，初始都为0，运行到一定次数才赋值,影响排列方式的选择
        vector<int> prodSeq(_types);
        for (size_t i = 0; i < prodSeq.size(); i++)
        {
            prodSeq[i] = i;
        }
        for (int run = 1; run <= repeat; run++)
        {
            vector<int> prodReq(_counts);
            int rawCount = 0;
            int maxRemainder = 0;
            int patterns = 0;
            vector<Plan> cutPlans;
            while (isReqLeft(prodReq))
            {
                int relaxH = (_rawLength / 20) > 300 ? 300 : (_rawLength / 20);
                int relaxRange = (13 * run) % relaxH;
                Plan plan = genAPlan(prodSeq, _lengths, prodReq, prodScore, relaxRange);
                for (size_t i = 0; i < prodReq.size(); i++)
                {
                    prodReq[i] -= plan.repeat * plan.ids[i];
                }
                cutPlans.push_back(plan);
                if (plan.remainder > maxRemainder)
                    maxRemainder = plan.remainder;
                rawCount += _rawLength * plan.repeat;
                patterns++;
            }
            notImprovedCount++;
            cout << cutPlans.size() << endl;
            if (bestRawCount > rawCount)
            {
                bestRawCount = rawCount;
                bestTail = maxRemainder;
                bestPlan = cutPlans;
                cout << bestPlan.size() << endl;
            }
            else if (bestRawCount == rawCount)
            {
                if (bestTail < maxRemainder || bestPlan.size() > patterns)
                {
                    bestTail = maxRemainder;
                    bestPlan = cutPlans;
                    cout << bestPlan.size() << endl;
                }
            }
            if (notImprovedCount >= 10)
            {
                genRandSeq(prodSeq);
                genRandScore(prodScore, _rawLength);
            }
            else
            {
                adjustProdSeq(prodSeq);
            }
        }
    }
    /**
     * 对[prodSeq] 打乱顺序
     */
    void genRandSeq(vector<int>& prodSeq)
    {
        shuffle(prodSeq.begin(), prodSeq.end(), default_random_engine(random_device()()));
    }
    void adjustProdSeq(vector<int>& prodSeq)
    {
        for (size_t i = 0; i < bestPlan.size(); i++)
        {
            int repeat = bestPlan[i].repeat;
            int rawRemain = bestPlan[i].remainder;
            if (repeat <= 1)
            {
                for (int id = 0; id < prodSeq.size(); id++)
                {
                    if (bestPlan[i].ids[id] > 0)
                    {
                        liftProdSeq(prodSeq, id);
                    }
                }
            }
        }
    }
    /**
     * 把指定的[idToLift]移动到Sequence前面
     */
    void liftProdSeq(vector<int>& prodSeq, int idToLift)
    {
        for (size_t i = 0; i < prodSeq.size(); i++)
        {
            if (prodSeq[i] == idToLift)
            {
                int p2 = i;
                int p1 = (p2 - 10) <= 0 ? 0 : (p2 - 10);
                for (int k = p2 - 1; k >= p1; k--)
                {
                    prodSeq[k + 1] = prodSeq[k];
                }
                prodSeq[p1] = idToLift;
                break;
            }
        }
    }
    void genRandScore(vector<int>& prodScore, int targetLen)
    {
        int t2 = targetLen / 2;
        int t3 = targetLen / 3;
        int t4 = targetLen / 4;
        int t5 = targetLen / 5;
        for (size_t i = 0; i < prodScore.size(); i++)
        {
            if (_lengths[i] >= t2)
                prodScore[i] = rand() % 80;
            else if (_lengths[i] >= t3)
                prodScore[i] = rand() % 40;
            else if (_lengths[i] >= t4)
                prodScore[i] = rand() % 30;
            else if (_lengths[i] >= t5)
                prodScore[i] = rand() % 20;
            else
                prodScore[i] = 0;
        }
    }
    bool isReqLeft(vector<int> numList)
    {
        for (size_t i = 0; i < numList.size(); i++)
        {
            if (numList[i] > 0)
                return true;
        }
        return false;
    }
    Plan genAPlan(vector<int>& prodSeq, vector<int>& prodLen, vector<int>& prodReq, vector<int>& prodScore, int relaxRange)
    {
        vector<int> lenList;
        vector<int> idList;
        int firstId = -1;
        int firstLen = 0;
        for (size_t i = 0; i < prodSeq.size(); i++)
        {
            int id = prodSeq[i];
            int req = prodReq[id];
            int len = prodLen[id];
            if (req > 0 && len <= _rawLength)
            {
                firstId = id;
                firstLen = len;
                break;
            }
        }
        Plan plan(_types);
        plan.remainder = _rawLength - firstLen;
        plan.ids[firstId] += 1;
        for (size_t i = 0; i < prodSeq.size(); i++)
        {
            int id = prodSeq[i];
            int req = prodReq[id];
            int len = prodLen[id];
            if (req > 0 && len <= _rawLength)
            {
                int maxNum = _rawLength / len;
                if (maxNum > req)
                    maxNum = req;
                if (id == firstId)
                    maxNum--;
                for (size_t j = 1; j <= maxNum; j++)
                {
                    lenList.push_back(len);
                    idList.push_back(id);
                }
            }
        }
        if (!lenList.empty())
        {
            vector<int> chosen = solveSubsetSum(lenList, idList, prodReq, prodScore, firstId, _rawLength - firstLen, relaxRange);
            if (!chosen.empty())
            {
                for (size_t i = 1; i < chosen.size(); i++)
                {
                    int id = chosen[i];
                    plan.ids[id] += 1;
                    plan.remainder -= prodLen[id];
                }
            }
        }
        int maxRepeat = inf;
        for (size_t i = 0; i < _types; i++)
        {
            if (plan.ids[i] > 0)
            {
                int repeat = prodReq[i] / plan.ids[i];
                if (repeat >= 1 && repeat <= maxRepeat)
                    maxRepeat = repeat;
            }
        }
        plan.repeat = maxRepeat;
        return plan;
    }
    vector<int> solveSubsetSum(vector<int>& candidateLen, vector<int>& candidateId, vector<int>& prodReq, vector<int>& prodScore, int firstId, int targetSum, int relaxRange)
    {
        vector<SumDetail> arr(targetSum + 1);
        vector<int> knownSum(targetSum + 1);
        int last = 0;
        int newlast = 0;
        for (int i = 0; i < candidateLen.size(); i++)
        {
            int sum1 = candidateLen[i];
            int id1 = candidateId[i];
            for (int j = 0; j <= last; j++)
            {
                int sum2 = knownSum[j];
                int mysum = sum1 + sum2;

                if (mysum > targetSum)
                {
                    continue;
                }
                int Sum = 0;
                for (int c = 1; c < arr[mysum].tempIds.size(); c++) {
                    Sum += _lengths[arr[mysum].tempIds[c]];
                }
                if (Sum > targetSum)
                    cout << "sum:" << Sum << "  mysum:" << mysum << "   targetsum:" << targetSum << endl;
                if (arr[mysum].hitTime == 0)
                {
                    arr[mysum].hitTime++;
                    vector<int> existIds = arr[sum2].tempIds;
                    existIds.push_back(id1);
                    arr[mysum].tempIds = existIds;
                    arr[mysum].planScore = scorePlan(arr[mysum].tempIds, prodReq, prodScore, firstId);
                    newlast += 1;
                    knownSum[newlast] = mysum;
                }
                else if (mysum >= targetSum - relaxRange * 1.2)
                {
                    arr[mysum].hitTime++;
                    if (arr[mysum].hitTime % 7 == 0)
                    {
                        vector<int> existIds(arr[sum2].tempIds);
                        vector<int> newIds =  existIds;
                        newIds.push_back(id1);
                        int score1 = arr[mysum].planScore;
                        int score2 = scorePlan(newIds, prodReq, prodScore, firstId);
                        if (score2 > score1)
                        {
                            int oldIdSum = 0;
                            for (int c = 1; c < arr[mysum].tempIds.size(); c++) {
                                oldIdSum += _lengths[arr[mysum].tempIds[c]];
                            }

                            int newIdSum = 0;
                            for (int c = 1; c < newIds.size(); c++) {
                                newIdSum += _lengths[newIds[c]];
                            }
                            if (newIdSum > targetSum)
                                cout << "sum1:" << sum1 << "  sum:" << newIdSum << "   targetsum:" << targetSum << endl;
                            arr[mysum].tempIds = newIds;
                            arr[mysum].planScore = score2;
                        }
                    }
                }
            }
            last = newlast;
        }
        int best = 0;//运行到光标处
        int bestScore = -inf;
        int range = (relaxRange >= targetSum) ? targetSum : relaxRange;
        for (int i = targetSum; i >= targetSum - range; i--)
        {
            if (arr[i].hitTime == 0)
                continue;
            int sum = 0;
            for (int c = 1; c < arr[i].tempIds.size(); c++) {
                sum += _lengths[arr[i].tempIds[c]];
            }
            if (sum > targetSum)
                cout << "sum:" << sum << endl;

            int score1 = scorePlan(arr[i].tempIds, prodReq, prodScore, firstId);
            if (score1 > bestScore)
            {
                bestScore = score1;
                best = i;
            }
        }
        if (best > 0) // 其他断点不要，就断这里
        { //接电话 畅连
            return arr[best].tempIds;
        }
        else
        {
            for (int i = targetSum; i >= 0; i--)
            {
                if (arr[i].hitTime > 0)
                {
                    return arr[i].tempIds;
                }
            }
            vector<int> Empty;
            Empty.push_back(-1);
            return Empty;
        }
    }
    int scorePlan(vector<int>& arr, vector<int>& prodReq, vector<int>& prodScore, int firstId)
    {
        Plan plan(_types);
        for (size_t i = 0; i < arr.size(); i++)
        {
            int id = arr[i];
            if (id > -1)
            {
                plan.ids[id] += 1;
            }
        }
        if (firstId >= 0)
        {
            plan.ids[firstId] += 1;
        }
        int combination = 0;
        for (size_t i = 0; i < _types; i++)
        {
            if (plan.ids[i] != 0)
                combination++;
        }
        if (combination > _maxCombination)
            return 0;
        int maxRepeat = inf;
        for (size_t i = 0; i < _types; i++)
        {
            if (plan.ids[i] <= 0)
                continue;
            int repeat = prodReq[i] / plan.ids[i];
            if (repeat < maxRepeat)
            {
                maxRepeat = repeat;
            }
        }
        int score = 0;
        int usage = 0;
        for (size_t i = 0; i < _types; i++)
        {
            if (plan.ids[i] > 0)
            {
                usage += _lengths[i] * plan.ids[i];
                score = usage + prodScore[i];
            }
        }
        score *= maxRepeat;
        return score;
    }

private:
    int _types;
    int _rawLength;
    int _maxCombination;
    int _retLen = 0;
    vector<int> _lengths;
    vector<int> _counts;
    vector<Plan> bestPlan;
};

//int main()
//{
//    int len[] = { 2000, 1800, 1700, 1560, 1310, 1060, 1000, 900, 820, 800, 630, 500, 400, 320 };
//    int cou[] = { 100, 100, 100, 14, 312, 18, 50, 56, 56, 56, 18, 34, 78, 292 };
//    //int len[] = {5,4,3,2,1};
//    //int cou[] = { 5,5,5,5,5 };
//    int* l = len;
//    int* c = cou;
//    int types = 14;
//    CuttingPlanner jobs(types, l, c, 5980, 5);
//    int* r = jobs.solve(10);
//    int length = jobs.getLen();
//    for (int i = 0; i < length; i++)
//    {
//        if (i % (types+2) == 0) cout << endl;
//        cout << *(r + i) << " ";
//    }
//    cout << length << endl;
//    system("pause");
//}